package ljl.alg.wangzheng_camp.round1.stack_and_queue;

import java.util.LinkedList;

/**
 * 官方四种解法，我一种也不会写！
 * */
public class _42_rain {
    
    /**
     *
     * */
    class cant_do {
        /*
         * 贪心思路：
         * 从前往后找，随便碰到两个，且举例大于 1 的，就累加一次雨水，
         * 正着一次反着一次，求 min
         * */
        public int trap(int[] height) {
            int n = height.length;
            int res = 0;
            int prevIndex = 0;
            while (prevIndex < n && height[prevIndex] == 0) prevIndex++;
            for (int i = prevIndex + 1; i < height.length; i++) {
                if (height[i] > 0 && i - prevIndex > 0) {
                    // 抱歉，编不下去了，我不会做
                }
            }
            return -1;
        }
    }
    
    // 暴力法，不要忘了人人都可以写 5 分钟的暴力法
    public int trap1(int[] height) {
        int n = height.length;
        int res = 0;
        for (int i = 1, l = n - 1; i < l; i++) {
            int maxLeft = 0, maxRight = 0;
            for (int j = i; j >= 0 ; j--) {
                if (height[j] > maxLeft) maxLeft = height[j];
            }
            for (int j = i; j < n; j++) {
                if (height[j] > maxRight) maxRight = height[j];
            }
            res += Math.min(maxLeft, maxRight) - height[i];
        }
        return res;
    }
    
    // 暴力法的优化，用两个数组存最大值，不用挨个找了
    // 这个解法已经快了很多很多很多，刚才要 1s，现在要 1ms
    public int trap2(int[] height) {
        int n = height.length;
        int[] lmax = new int[n];
        int[] rmax = new int[n];
        lmax[0] = height[0];
        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(height[i], lmax[i - 1]);
        }
        rmax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(height[i], rmax[i + 1]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.min(lmax[i], rmax[i]) - height[i];
        }
        return res;
    }
    
    // 考点 2，单调栈
    public int trap3(int[] height) {
        LinkedList<Integer> stack = new LinkedList<>();
        int cur = 0, n = height.length;
        int res = 0;
        while (cur < n) {
            /* 这写成 stack.peek() 而不是 height[stack.peek()] 找了十分钟没找到原因？*/
            while (!stack.isEmpty() && height[stack.peek()] < height[cur]) {
                int last = stack.pop();
                if (stack.isEmpty()) break;
                res += (Math.min(height[cur], height[stack.peek()]) - height[last]) * (cur - stack.peek() - 1);
            }
            stack.push(cur++);
        }
        return res;
    }
    
    // 我不知道双指针为什么是对的
    public int trap4(int[] height) {
        int l = 0, r = height.length - 1;
        int res = 0;
        int lmax = 0, rmax = 0;
        while (l <= r) {
            if (height[l] <= height[r]) {
                if (height[l] > lmax) lmax = height[l];
                else res += lmax - height[l];
                l++;
            } else {
                if (height[r] > rmax) rmax = height[r];
                else res += rmax - height[r];
                r--;
            }
        }
        return res;
    }
    class of {
        public int trap4(int[] height) {
            int left = 0, right = height.length - 1;
            int ans = 0;
            int left_max = 0, right_max = 0;
            while (left < right) {
                if (height[left] < height[right]) {
                    if (height[left] >= left_max) {
                        left_max = height[left];
                    } else {
                        ans += (left_max - height[left]);
                    }
                    ++left;
                } else {
                    if (height[right] >= right_max) {
                        right_max = height[right];
                    } else {
                        ans += (right_max - height[right]);
                    }
                    --right;
                }
            }
            return ans;
        }
    }
}
